/*
 * Saphre - Suffix Arrays for Phrase Extraction
 * Copyright (C) 2013 
 * Dale Gerdemann - Tübingen, Germany 
 * Niko Schenk - Frankfurt am Main, Germany
 * All rights reserved.
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */
package collectors.impl.visitors;

import util.Interval;
import saphre.core.Store;
import saphre.core.SuffixArray;
import java.util.List;

/**
 * Basic top down traversal. Collects all phrases (maximal repeats) but no
 * associated statistics such as tf or df.
 * 
 * @author Dale Gerdemann
 */
public class TopDownTraversal {

    /**
     * Top-down traversal of lcp-interval tree 
     * @param inter
     * @param tab
     * @param lcp
     * @param sa
     * @param store
     * @param result 
     */
    public static void td(Interval inter, String tab, int lcp,
            SuffixArray sa, Store store, List<String> result) {

        if (!inter.trivial()) {
            int mid = sa.cldtab[inter.lb()];
            if (mid <= inter.lb() || mid > inter.rb()) {
                mid = sa.cldtab[inter.rb()];
            }
            Interval left = new Interval(inter.lb(), mid - 1);
            Interval right = new Interval(mid, inter.rb());
            if (lcp < sa.lcptab[mid]) {
                lcp = sa.lcptab[mid];
                boolean leftVariable = false;
                int b = store.text[sa.suftab[inter.lb()] - 1];
                for (int i = inter.lb() + 1; i <= inter.rb(); i++) {
                    if (store.text[sa.suftab[i] - 1] != b) {
                        leftVariable = true;
                        break;
                    }
                }
                if (leftVariable && lcp > 1 && lcp < 8) {
                    int loc = sa.suftab[inter.lb()];
                    result.add(store.toString(loc, loc + lcp));
                }
                tab = tab + "  ";
            }
            td(left, tab, lcp, sa, store, result);
            td(right, tab, lcp, sa, store, result);
        }
    }
}
